package com.zhanghp.class03;

import com.zhanghp.utils.CommonUtils;

import java.util.Deque;
import java.util.LinkedList;

/**
 * <h1>双链表 实现 双端队列</h1>
 *
 * @author zhanghp
 * @since 2023/10/11 18:16
 */
public class Code03_DoubleLinkedListToDeque {
    public static void main(String[] args) {
//        MyDeque<Integer> deque = new MyDeque<>();
//        deque.pushHead(1);
//        deque.pushTail(2);
//        deque.pushTail(3);
//        deque.printDeque();
        Calipers();
//        testDeque();
    }

    private static void Calipers() {
        Deque<Integer> deque = new LinkedList<>();
        MyDeque<Integer> myDeque = new MyDeque<>();
        int test_time = 10;
        for (int i = 0; i < test_time; i++) {
            double random = Math.random();
            if (random < 0.2) {
                int maxValue = (int) (Math.random() * 100);
                double pushPro = Math.random();
                if (pushPro < 0.5) {
                    deque.addFirst(maxValue);
                    myDeque.pushHead(maxValue);
                } else {
                    deque.addLast(maxValue);
                    myDeque.pushTail(maxValue);
                }

            } else if (random < 0.4) {
                if (!myDeque.isEmpty()) {
                    int dpf = 0;
                    int mph = 0;
                    mph = deque.pollFirst();
                    dpf = myDeque.pollHead();
                    if (dpf != mph) {
                        System.out.println("Fuck pollFirst, number don not match");
                        return;
                    }
                }
            } else if (random < 0.6) {
                if (!myDeque.isEmpty()) {
                    int dpf = 0;
                    int mph = 0;
                    mph = deque.pollLast();
                    dpf = myDeque.pollTail();
                    if (dpf != mph) {
                        System.out.println("Fuck pollLast, number don not match");
                        return;
                    }
                }
            } else if (random < 0.8) {
                if (!myDeque.isEmpty()) {
                    int dpf = 0;
                    int mph = 0;
                    mph = myDeque.peekHead();
                    dpf = deque.peekFirst();
                    if (dpf != mph) {
                        System.out.println("Fuck peekFirst, number don not match");
                        return;
                    }
                }
            } else {
                if (!myDeque.isEmpty()) {

                    int dpf = 0;
                    int mph = 0;
                    mph = deque.peekLast();
                    dpf = myDeque.peekTail();
                    if (dpf != mph) {
                        System.out.println("Fuck PeekTail, number don not match");
                        return;
                    }
                }
            }
        }
        if (deque.size() != myDeque.size) {
            System.out.println("Fuck, size do not match");
        }

    }

    public static void testDeque() {
        MyDeque<Integer> myDeque = new MyDeque<>();
        Deque<Integer> test = new LinkedList<>();
        int testTime = 5000000;
        int maxValue = 200000000;
        System.out.println("测试开始！");
        for (int i = 0; i < testTime; i++) {
            if (myDeque.isEmpty() != test.isEmpty()) {
                System.out.println("Oops!");
            }
            if (myDeque.size() != test.size()) {
                System.out.println("Oops!");
            }
            double decide = Math.random();
            if (decide < 0.33) {
                int num = (int) (Math.random() * maxValue);
                if (Math.random() < 0.5) {
                    myDeque.pushHead(num);
                    test.addFirst(num);
                } else {
                    myDeque.pushTail(num);
                    test.addLast(num);
                }
            } else if (decide < 0.66) {
                if (!myDeque.isEmpty()) {
                    int num1 = 0;
                    int num2 = 0;
                    if (Math.random() < 0.5) {
                        num1 = myDeque.pollHead();
                        num2 = test.pollFirst();
                    } else {
                        num1 = myDeque.pollTail();
                        num2 = test.pollLast();
                    }
                    if (num1 != num2) {
                        System.out.println("Oops!");
                    }
                }
            } else {
                if (!myDeque.isEmpty()) {
                    int num1 = 0;
                    int num2 = 0;
                    if (Math.random() < 0.5) {
                        num1 = myDeque.peekHead();
                        num2 = test.peekFirst();
                    } else {
                        num1 = myDeque.peekTail();
                        num2 = test.peekLast();
                    }
                    if (num1 != num2) {
                        System.out.println("Oops!");
                    }
                }
            }
        }
        if (myDeque.size() != test.size()) {
            System.out.println("Oops!");
        }
        while (!myDeque.isEmpty()) {
            int num1 = myDeque.pollHead();
            int num2 = test.pollFirst();
            if (num1 != num2) {
                System.out.println("Oops!");
            }
        }
        System.out.println("测试结束！");
    }

    // 对数器---------------------------------------------》

    public static class Node<V> {
        public V value;
        public Node<V> pre;
        public Node<V> next;

        public Node(V v) {
            value = v;
            pre = null;
            next = null;
        }
    }

    public static class MyDeque<V> {
        public Node<V> head;
        public Node<V> tail;
        public int size;

        /**
         * 头部插入
         *
         * @param v 值
         */
        public void pushHead(V v) {
            Node<V> cur = new Node<>(v);
            if (head == null) {
                head = cur;
                tail = cur;
            }else {
                cur.next = head;
                head.pre = cur;
                head = cur;
            }
            size++;
        }


        /**
         * 尾部插入
         *
         * @param v 值
         */
        public void pushTail(V v) {
            Node<V> cur = new Node<>(v);
            if (tail == null) {
                tail = cur;
                head = cur;
            }else {
                tail.next = cur;
                cur.pre = tail;
                tail = cur;
            }
            size++;
        }

        /**
         * 弹出头部
         *
         * @return 头部值
         */
        public V pollHead() {
            V ans = null;
            if (head == null) {
                return ans;
            }
            size--;
            ans = head.value;
            if (head == tail) {
                head = null;
                tail = null;
            } else {
                head = head.next;
                head.pre = null;
            }
            return ans;

        }

        /**
         * 弹出尾部
         *
         * @return 尾部值
         */
        public V pollTail() {
            V ans = null;
            if (tail == null) {
                return ans;
            }
            size--;
            ans = tail.value;
            if (tail == head) {
                head = null;
                tail = null;
            } else {
                tail = tail.pre;
                tail.next = null;
            }
            return ans;
        }

        /**
         * 查看头部，不弹出
         *
         * @return 头部值
         */
        public V peekHead() {
            return head == null ? null : head.value;
        }

        /**
         * 查看尾部
         *
         * @return 尾部值
         */
        public V peekTail() {
            return tail == null ? null : tail.value;
        }

        /**
         * 是否为空
         *
         * @return true-是 false-否
         */
        public boolean isEmpty() {
            return size == 0;
        }

        /**
         * 双端队列容量
         *
         * @return 容量大小
         */
        public int size() {
            return size;
        }

        /**
         * 打印
         */
        public void printDeque() {

            System.out.printf("%s%n", "打印顺序：头 -》 尾");
            if (head == null) {
                System.out.printf("%s%n", "头部为空");
            } else {
                Node<V> curHead = head;
                do {
                    System.out.printf("%s ", curHead.value);
                    curHead = curHead.next;
                } while (curHead != null);
            }

            CommonUtils.printDivingLine();

            System.out.printf("%s%n", "打印顺序：尾 -》头");
            if (tail == null) {
                System.out.printf("%s%n", "尾部为空");
            } else {
                Node<V> curTail = tail;
                do {
                    System.out.printf("%s ", curTail.value);
                    curTail = curTail.pre;
                } while (curTail != null);
            }

        }

    }

}
